\documentclass[UTF8]{ctexart}
\usepackage{xltxtra}
\usepackage{geometry}
\usepackage{xcolor}
\usepackage{amsmath}
\usepackage{cases}
\usepackage{extarrows}
\usepackage{amsfonts}
\usepackage{longtable}
\usepackage{booktabs}
\usepackage{amssymb}
\usepackage{tabularray}
\geometry{a4paper, left=2cm, right=2cm, top=4cm, bottom=4cm}

\title{硬币找零问题}
\author{Goodtea}

\newtheorem{example}{例}[section]

  
\begin{document}  
  
\maketitle  
  
\section{算法}

定义状态\verb|dp[i][j]|，含义是前i种硬币凑成金额j所需的最小硬币数。

步骤如下：

1. 初始化\verb|dp[0][0] = 0|，其他为无穷大。

\verb|i=0,dp[i][0]=0|表示金额为0，硬币数量为0。
在这个基础上加一个1分硬币，
前进到金额\verb|i=1|、硬币数量\verb|dp[1][1]=dp[0][0]+1=dp[1-1][1-1*1]+1=1|的情况，
同理\verb|dp[1][2]=dp[1-1][1-2*1]+2=2|。

得到递推关系式\verb|dp[i][j] = min(dp[i][j],dp[i-1][j-1*coins[i-1]]+k)|

2. 在使用1分硬币的基础上增加使用5分硬币。
比5分硬币小的金额不可能用5分硬币实现，
所以当\verb|i=5|时，相当于在\verb|i=0|的基础上加了一个5分硬币，
得到\verb|dp[2][5]=dp[2-1][5-1*5]+1=1|。同理\verb|dp[2][6]=dp[2-1][6-1*5]+1=2|。

得到递推关系式\verb|dp[i][j] = min(dp[i][j],dp[i-1][j-1*coins[i-1]]+k)|

3. 继续寻找其他面值的硬币。

4. 最终结果即为\verb|dp[n][money]|

\paragraph{Hint} 每一步增加硬币种类时需要限制每一个硬币的最大数，故引入\verb|MaxCount|变量限制此时可用最大数

\section{函数设计}  
分别输入每种硬币的最大数量与目标总金额，每种硬币均不能超过其最大数量，用动态规划求解所需硬币总数的最小值。
  
\subsection{输入}
\verb|coins| 币种

\verb|MAX| 各币种最大数目

\verb|n|  币种数

\verb|money| 目标总金额

  
\section{测试}  
  
该函数已使用各种测试用例进行测试，以确保其正确性和效率。已使用以下测试用例：  
  
\begin{example}
    请依次输入币值分别为1,5,10,25美分的硬币最大数量: 
    
    1 美分: \textbf{0}

    5 美分: \textbf{1}

    10 美分: \textbf{1}

    25 美分: \textbf{1}

    请输入要求达到的总金额目标数: \textbf{6}
\end{example} 
\verb|无法凑出目标总金额| 


\begin{example}
    请依次输入币值分别为1,5,10,25美分的硬币最大数量: 
    
    1 美分: \textbf{1}

    5 美分: \textbf{1}

    10 美分: \textbf{1}

    25 美分: \textbf{1}

    请输入要求达到的总金额目标数: \textbf{6}
\end{example} 
\verb|总金额为6时所需硬币总数的最小值为: 2| 


\begin{example}
    请依次输入币值分别为1,5,10,25美分的硬币最大数量: 
    
    1 美分: \textbf{9}

    5 美分: \textbf{}

    10 美分: \textbf{9}

    25 美分: \textbf{9}

    请输入要求达到的总金额目标数: \textbf{99}
\end{example} 
\verb|总金额为99时所需硬币总数的最小值为: 9| 


\begin{example}
    请依次输入币值分别为1,5,10,25美分的硬币最大数量: 
    
    1 美分: \textbf{3}

    5 美分: \textbf{3}

    10 美分: \textbf{3}

    25 美分: \textbf{3}

    请输入要求达到的总金额目标数: \textbf{99}
\end{example} 
\verb|无法凑出目标总金额| 
  
\end{document}  